package SortAlgorithm;

/**
 * 题目 ：数组的相对排序
 * 题目详述 ：
 * 给你两个数组，arr1 和arr2，arr2中的元素各不相同，arr2 中的每个元素都出现在arr1中。
 * 对 arr1中的元素进行排序，使 arr1 中项的相对顺序和arr2中的相对顺序相同。
 * 未在arr2中出现过的元素需要按照升序放在arr1的末尾。
 *
 * 提示:
 * （1）1 <= arr1.length, arr2.length <= 1000
 * （2）0 <= arr1[i], arr2[i] <= 1000
 * （3）arr2中的元素arr2[i]各不相同
 * （4）arr2 中的每个元素arr2[i]都出现在arr1中
 *
 */
public class RelativeSortArray {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        // 由于1 <= arr1, arr2 <= 1000，即arr1数组中元素总数不会大于1000；
        // （即，arr1中数组中所有元素值的取值范围 ：[0 , 1000]）
        // ===》 那么只需要建立一个大小为1000的统计数组（用来统计arr1中每个元素出现的次数）
        int[] counts = new int[1001];
        // 遍历arr1数组，来统计arr1数组中每个元素出现的次数；
        for (int i : arr1) {
            counts[i]++;
        }

        // 由于需要将arr1数组中的所有元素按照arr2数组中元素顺序进行排序；
        // 即，通过将arr1数组中的所有元素都记录到counts数组中，利用counts数组作为中间件
        // 遍历arr2数组，通过counts数组（之前已经统计过arr1数组中每个元素出现的次数），来重新构建arr1数组（等价于对于arr1中数组元素进行重排）
        int k = 0;
        for (int i : arr2) {
            // while循环遍历，直至arr2中正在遍历的元素在counts数组中统计次数 == 0
            while(counts[i] > 0){
                arr1[k++] = i;
                counts[i]--;
            }
        }

        // 处理arr1数组中出现的，但是未在arr2数组中出现的元素的排序问题；
        for(int i = 0 ; i < counts.length ; i++){
            // 即，通过遍历整个counts数组（统计arr1数组中元素出现次数）,来获取那些元素还未进行处理
            while(counts[i] > 0){
                arr1[k++] = i;
                counts[i]--;
            }
        }
        return arr1;
    }
    /**
     * 计数排序算法 ：
     * （1）使用辅助数组统计nums目标数组中元素出现次数；
     * 注意 ：辅助数组counts的大小是根据nums目标数组中的取值范围来决定的；
     * （2）遍历整个counts辅助数组，来重新构建排序好的nums目标数组；
     * a.若是从大到小排序的话，从counts数组的尾元素遍历到头元素，构建nums目标数组，同时将counts辅助数组中值--；
     * b若是从到小排序的话，从counts数组的尾元素遍历到头元素，构建nums目标数组，同时将counts辅助数组中值--；
     *
     *
     * 时间复杂度 ：O（m + n）（m，为数组arr1的长度；同时，n为数组arr2的长度）；
     *
     */
}

